package lhz.algorithm.chapter.five;

/**
 * 随机数组两种实现，《算法导论》第五章第三节
 * 
 * @author lihzh
 */
public class RandomArray {

	private static int[] arrayOne = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
			11, 12, 13 };
	private static int[] arrayTwo = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
			11, 12, 13 };

	public static void main(String[] args) {
		//随机方式一，排列数组一
		permuteBySorting(arrayOne);
		//打印数组一
		printArray(arrayOne);
		System.out.println("");
		//随机方式二，排列数组二
		randomizeInPlace(arrayTwo);
		//打印数组二
		printArray(arrayTwo);
	}

	/**
	 * 随机化数组方式一，采用优先级数组比照方式
	 * PERMUTE-BY-SORTING(A) 
	 * 1 n ← length[A] 
	 * 2 for i ← 1 to n 
	 * 3 do P[i] =RANDOM(1, n^3) 
	 * 4 sort A, using P as sort keys 
	 * 5 return A
	 */
	private static void permuteBySorting(int[] input) {
		int n = input.length;
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = randomValue(n);
		}
		mergeSort(input, p);
		/*
		 *复杂度分析：
		 *因为采用了合并排序，所以可知复杂度为:Θ(n lg n) 
		 */
	}
	
	/**
	 * 随机化数组方式二，直接位置交换方式
	 * 复杂度为：O(n)
	 * RANDOMIZE-IN-PLACE(A)
	 *	1 n ← length[A]
	 *	2 for i ← to n
	 *	3 do swap A[i] ↔ A[RANDOM(i, n)]
	 * @param input
	 */
	private static void randomizeInPlace(int[] input) {
		int n = input.length;
		for (int i = 0; i < n; i++) {
			int index = (int) (Math.random() * (n - i - 1) + i);
			int temp = input[index];
			input[index] = input[i];
			input[i] = temp;
		}
	}
	
	/**
	 * 产生从1到n^3的随机数
	 * @param n
	 * @return
	 */
	private static int randomValue(int n) {
		return (int) (Math.random() * (n * n * n - 1) + 1);
	}

	/**
	 * 改写的合并排序，根据数组P中定义的优先级决定顺序。
	 * @param array
	 * @return
	 */
	private static int[] mergeSort(int[] array, int[] keyArray) {
		// 如果数组的长度大于1，继续分解数组
		if (array.length > 1) {
			int leftLength = array.length / 2;
			int rightLength = array.length - leftLength;
			// 创建两个新的数组
			int[] left = new int[leftLength];
			int[] right = new int[rightLength];
			// 创建两个新的key数组
			int[] leftKey = new int[leftLength];
			int[] rightKey = new int[rightLength];
			// 将array中的值分别对应复制到两个子数组中
			for (int i = 0; i < leftLength; i++) {
				left[i] = array[i];
				leftKey[i] = keyArray[i];
			}
			for (int i = 0; i < rightLength; i++) {
				right[i] = array[leftLength + i];
				rightKey[i] = keyArray[leftLength + i];
			}
			// 递归利用合并排序，排序子数组
			left = mergeSort(left,leftKey);
			right = mergeSort(right,rightKey);
			// 设置初始索引
			int i = 0;
			int j = 0;
			for (int k = 0; k < array.length; k++) {
				// 如果左边数据索引到达边界则取右边的值
				if (i == leftLength && j < rightLength) {
					array[k] = right[j];
					j++;
					// 如果右边数组索引到达边界，取左数组的值
				} else if (i < leftLength && j == rightLength) {
					array[k] = left[i];
					i++;
					// 如果均未到达，则根据优先级数组中的顺序取值
				} else if (i < leftLength && j < rightLength) {
					if (leftKey[i] > rightKey[j]) {
						array[k] = right[j];
						j++;
					} else if (leftKey[i] < rightKey[j]){
						array[k] = left[i];
						i++;
					} 
				}
			}
		}
		return array;
	}
	
	private static void printArray(int[] array) {
		for (int i : array) {
			System.out.print(i + " ");
		}
	}

}
